\documentclass{article}

\usepackage{listings}

\title{HA2 - Uebung 3}
\author{Leonardo Balestrieri, Marco Traeger}

\lstset{ %
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\tiny,      % the size of the fonts that are used for the line-numbers
stepnumber=5,                   % the step between two line-numbers.
tabsize=2
}

\begin{document}
\parindent 0pt %keine Zeileneinrueckungen

\maketitle

\lstset{language=java}
\begin{lstlisting}
	/**
	 * Fast Discrete Fourier transformation.
	 * 
	 * Calculates the dft of the polynome
	 * <tt>p[0] .. p[n]</tt> with the primitive (n+1)-unit-root.
	 * 
	 * This method is in-place on <tt>p</tt>; the result of the transformation is
	 * store in <tt>p[0] .. p[n]</tt>.
	 * 
	 * Note: Even through this algorithm works inplace on p it's still allocs
	 * (n+1)*(log(n+1) - 1) storage for it's execution for it's recursive calls.
	 * 
	 * @param p coefficient of the polynome
	 * @param n (n+1) are the number of coefficients of the polynome
	 * @param omega primitive (n+1)-unitroot
	 * @pre <tt>(n+1)/2 = 2^k for a k in N</tt> 
	 * @pre <tt>p.length >= n+1</tt>
	 * @pre <tt>omega is n+1-unitroot</tt>
	 */
	public void fft(F[] p, int n, F omega) {
		if(n == 0) {
			/*
			 * nothing to do because the method works in-place on p
			 */
			return;
		}
		else {
			/*
			 * (n-1)/2 once, just a computation optimation.
			 * note: by precondition n+1 = 2^k for a k in N and
			 * m = (n-1)/2 = (n+1)/2 - 1 = 2^(k-1) - 1.
			 */
			int m = (n-1) >> 1;
			
			/*
			 * create ag and au
			 */
			@SuppressWarnings("unchecked")
			F[] ag = (F[]) new Object[m+1];
			@SuppressWarnings("unchecked")
			F[] au = (F[]) new Object[m+1];
			
			for(int i = 0; i <= m; i++) {
				// 2*i = i<<1
				ag[i] = p[(i<<1)];
				au[i] = p[(i<<1)+1];
			}
			
			/*
			 *  dfts of half size:
			 *  because the implementation is inplace
			 *  ag := u := fft(ag,m,omega^2);
			 *  au := v := ftt(au,m,omega^2);
			 */
			fft(ag, m, field.square(omega));
			fft(au, m, field.square(omega));
			
			F w = field.one();
			for(int i = 0; i <= m; i++) {
				p[i]     = field.add(ag[i],field.mul(w, au[i]));
				p[m+1+i] = field.sub(ag[i],field.mul(w, au[i]));
				
				// w := w * omega
				w = field.mul(w, omega);
			}
		}
	}
\end{lstlisting}

\lstset{language=java}
\begin{lstlisting}
	/**
	 * Inverse Fast Discrete Fourier transformation.
	 * Calculates the idft of the polynome
	 * <tt>p[0] .. p[n]</tt> with the primitive (n+1)-unit-root.
	 * 
	 * This method is in-place on <tt>p</tt>; the result of the transformation is
	 * store in <tt>p[0] .. p[n]</tt>.
	 * 
	 * Note: Even through this algorithm works inplace on p it's still allocs
	 * (n+1)*(log(n+1) - 1) storage for it's execution for it's recursive calls.
	 * 
	 * @param p coefficient of the polynome
	 * @param n (n+1) are the number of coefficients of the polynome
	 * @param omega primitive (n+1)-unitroot for the dft,
	 * this idft algorithm will calculate the inverse of the unit-root
	 * on it's own.
	 * @pre <tt>(n+1)/2 = 2^k for a k in N</tt>
	 * @pre <tt>p.length >= n+1</tt>
	 * @pre <tt>omega is n+1-unitroot</tt>
	 */
	public void ifft(F[] p, int n, F omega) {
		fft(p,n,field.inverseMul(omega));
		
		/*
		 * div result by n+1
		 */
		// create the number n+1 of the field.
		F nplusone = field.addOneNTimes(n+1);

		for(int i = 0; i <= n; i++) {
			p[i] = field.div(p[i], nplusone);
		}
	}
\end{lstlisting}

\end{document}